/*    Copyright 2010 Tobias Marschall
 *
 *    This file is part of MoSDi.
 *
 *    MoSDi is free software: you can redistribute it and/or modify
 *    it under the terms of the GNU General Public License as published by
 *    the Free Software Foundation, either version 3 of the License, or
 *    (at your option) any later version.
 *
 *    MoSDi is distributed in the hope that it will be useful,
 *    but WITHOUT ANY WARRANTY; without even the implied warranty of
 *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *    GNU General Public License for more details.
 *
 *    You should have received a copy of the GNU General Public License
 *    along with MoSDi.  If not, see <http://www.gnu.org/licenses/>.
 */

package mosdi.fa;

import java.util.List;

import mosdi.util.BitArray;

/** Represents a string, where each position consists of a set of characters. */
public class GeneralizedString implements Comparable<GeneralizedString>{
	private BitArray[] positions;
	private Alphabet alphabet;

	/** Constructs the generalized string from a simple string allowed to contain
	 *  wildcards ("?").*/
	public GeneralizedString(Alphabet alphabet, String s) {
		this.alphabet=alphabet;
		positions = new BitArray[s.length()];
		for (int i=0; i<s.length(); ++i) {
			positions[i]=new BitArray(alphabet.size());
			if (s.charAt(i)=='?') {
				positions[i].invert();
			} else {
				int index = alphabet.getIndex(s.charAt(i));
				if (index<0) throw new IllegalArgumentException(String.format("Unknown character \"%s\" encountered", s.charAt(i)));
				positions[i].set(index, true);				
			}
		}
	}
	
	/** General constructor. Expects for each position the set of expected
	 *  characters in terms of a BitArray (w.r.t. the alphabet). */
	public GeneralizedString(Alphabet alphabet, BitArray[] positions) {
		this.positions=positions;
		this.alphabet=alphabet;
	}

	/** General constructor. Expects for each position the set of expected
	 *  characters in terms of a BitArray (w.r.t. the alphabet). */
	public GeneralizedString(Alphabet alphabet, List<BitArray> positions) {
		this.positions=new BitArray[positions.size()];
		int i=0;
		for (BitArray ba : positions) this.positions[i++]=ba;
		this.alphabet=alphabet;
	}

	/** Constructor for a single letter string. */
	public GeneralizedString(Alphabet alphabet, BitArray charSet) {
		this.alphabet=alphabet;
		this.positions=new BitArray[1];
		this.positions[0]=charSet;
	}
	
	/** Concatenates this string with another (over the same alphabet). */
	public void concat(GeneralizedString gs) {
		BitArray[] newPositions = new BitArray[this.positions.length+gs.positions.length];
		System.arraycopy(this.positions, 0, newPositions, 0, this.positions.length);
		System.arraycopy(gs.positions, 0, newPositions, this.positions.length, gs.positions.length);
		positions=newPositions;
	}

	/** Concatenates a list of BitArrays (over the same alphabet) to this. */
	public void concat(List<BitArray> l) {
		BitArray[] newPositions = new BitArray[this.positions.length+l.size()];
		System.arraycopy(this.positions, 0, newPositions, 0, this.positions.length);
		int i = this.positions.length;
		for (BitArray ba : l) {
			newPositions[i++]=ba;
		}
		positions=newPositions;
	}
	
	public GeneralizedString suffix(int length) {
		if ((length>length()) || length<0) throw new IllegalArgumentException();
		BitArray[] positions = new BitArray[length];
		int n = length() - length;
		for (int i=0; i<length; ++i) positions[i] = new BitArray(this.positions[i+n]);
		return new GeneralizedString(alphabet, positions);
	}

	public GeneralizedString prefix(int length) {
		if ((length>length()) || length<0) throw new IllegalArgumentException();
		BitArray[] positions = new BitArray[length];
		for (int i=0; i<length; ++i) positions[i] = new BitArray(this.positions[i]);
		return new GeneralizedString(alphabet, positions);
	}

	public BitArray getPosition(int index) { return positions[index]; }
	
	public int length() { return positions.length; }
	
	/** Returns true if the this generalized string matches the given string 
	 *  starting from given position, i.e. checks if the generalized string matches
	 *  s.substr(position,position+this.length()). */
	public boolean matches(String s, int position) {
		boolean mapUnknown = alphabet.contains('#');
		for (int i=0; i<positions.length; ++i) {
			if (i+position>=s.length()) return false;
			char c = s.charAt(i+position);
			// map all other (those not in the pattern) characters onto #
			int index = alphabet.getIndex(c);
			if (index<0) {
				if (mapUnknown) c='#';
				else throw new IllegalArgumentException(String.format("Unknown character \"%s\" encountered", c));
			}
			if (!positions[i].get(index)) return false;
		}
		return true;
	}
	
	/**
	 * TODO: wird noch getestet
	 * 
	 * Decides whether a given String is a substing of this generalised string from a given Offset<br>
	 * [ this.subset(position, this.length).contains( s ) ]  
	 * 
	 * @param s a String 
	 * @param position offset for THIS string.
	 * @return true iff this.matchesFrom(s, position)

	 *             012345 <br>
	 * this     = "ACCAGT"<br>
	 * s_1      = "AG"    <br>
	 * s_2      = "AT"    <br>
	 * s_3      = "GT"    <br>
	 * position = 3       <br>
	 * 
	 * matchesFrom(s_1, position) = true   <br>
	 * matchesFrom(s_2, position) = false  <br>
	 * matchesFrom(s_3, 4) = true          <br>
	 */
	public boolean matchesFrom(String s, int position) {
		boolean mapUnknown = alphabet.contains('#');
		if(positions.length - position < s.length()) {
			return false;
		} else {
			for(int i = position; i<positions.length; ++i) {
				char c = s.charAt(i);
				int index = alphabet.getIndex(c);
				if (index<0) {   //extracted Character from s does not exist in alphabet
					if (mapUnknown)
						c='#';
					else 
						throw new IllegalArgumentException(String.format("Unknown character \"%s\" encountered", c));
				}
				if (!positions[i].get(index)) //Characters match
					return false;
			}
			return true;
		}
	}
	
	/**
	 * Checks whether a given char c matches this.GeneralizedString at position "position" 
	 * @param c a char
	 * @param position the position in this.GeneralizedString where matching shall be checked
	 * @return true iff c matches at this.GeneralizedString[position]
	 */
	public boolean matchesAt(char c, int position) {
		//boolean mapUnknown = alphabet.contains('#');
		if( position < 0 || position >= positions.length) {
			throw new IllegalArgumentException("Invalid Positionparameter: "+position);
		}
		int index = alphabet.getIndex(c);
		if(positions[position].get(index)) {
			return true;
		}
		return false;
	}

	
	/** Returns true if the generalized string is compatible with another, given 
	 *  generalized string. Two generalized strings are compatible if they have the
	 *  same length and there exists a string that matches both generalized strings.
	 */
	public boolean compatible(GeneralizedString gs) {
		if (!alphabet.equals(gs.getAlphabet())) return false;
		if (length()!=gs.length()) return false;
		for (int i=0; i<length(); ++i) {
			BitArray ba = new BitArray(positions[i]);
			ba.and(gs.getPosition(i));
			if (ba.allZero()) return false;
		}
		return true;
	}
	
	public String toString() {
		StringBuffer sb = new StringBuffer();
		for (BitArray ba : positions) {
			sb.append("(");
			int i=-1;
			for (boolean b : ba) {
				++i;
				if (!b) continue;
				sb.append(alphabet.get(i));
			}
			sb.append(")");
		}
		return sb.toString();
	}

	public Alphabet getAlphabet() {
		return alphabet;
	}
	
	/** Returns the probability that this generalized string occurs. */
	public double getProbability(double[] characterDistribution) {
		double result = 1.0;
		for (BitArray ba : positions) {
			double p = 0.0;
			for (int i=0; i<ba.size(); ++i) {
				if (ba.get(i)) p+=characterDistribution[i];
			}
			result*=p;
		}
		return result;
	}
	
	public BitArray[] getPositions() { return positions; }

	public int compareTo(GeneralizedString gs) {
		//not the most effizient method
		return this.toString().compareTo(gs.toString());
	}
}
